// https://leetcode.cn/problems/subsets-ii/
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    // 最笨的方法
    vector <vector<int>> subsetsWithDup(vector<int> &nums) {
        vector <vector<int>> res;
        set <vector<int>> s;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        vector<int> em = {};
        s.insert(em);
        for (int i = 0; i < len; i++) {
            set <vector<int>> tmpS;
            for (auto j : s) {
                j.push_back(nums[i]);
                tmpS.insert(j);
            }
            for (auto j : tmpS) {
                s.insert(j);
            }
        }
        for (auto i : s) {
            res.push_back(i);
        }
        return res;
    }

    // dfs 版本
    vector <vector<int>> subsetsWithDup1(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        set <vector<int>> s;
        vector <vector<int>> res;
        int len = nums.size();
        vector<int> tmp;
        auto dfs = [&](auto &&me, int index) {
            if (index == len) {
                s.insert(tmp);
                return;
            }
            tmp.push_back(nums[index]);
            me(me, index + 1);
            tmp.pop_back();
            me(me, index + 1);
        };
        dfs(dfs, 0);
        for (auto i : s) {
            res.push_back(i);
        }
        return res;
    }
};


int main() {

    Solution so;
    vector<int> nums = {1, 2, 2};
    // vector<int> nums = {1,2,2};
    auto res = so.subsetsWithDup1(nums);
    for (auto item : res) {
        for (auto i : item) {
            cout << i << ",";
        }
        cout << endl;
    }
    return 0;
}